教學來源:
如何用程式進行質因數分解和尋找最大公因數與最小公倍數？

b為a的因數(Factor)，
a為 b的倍數(Multiple)

8 的 因數 有 1 、2、 4、 8
4 的 因數 有 1 、 2 、 4
8和4 的 公因數 會是 1、2、4(Common Divisor)

8和4 的 最大公因數 會是 4 (Greatest Common Divisor，簡稱GCD)

4 的倍數有 : 4 * 1 、4 * 2、4 * 3 ……………
8 的倍數有 : 8 * 1 、 8 * 2、8 * 3……………..

4 和 8 的 公倍數 有無限多個 ，所以只找最小公倍數 (Least Common Multiple，簡稱LCM)

4 和 8 的 LCM 就是8

質數 就是 之前數學課背的:
2、3、5、7、11、13、17、19
、23、29……………….

質數 就是 只能 自己 和 1 相乘 來表示

2 = 2 * 1
29 = 29 * 1

要判斷一個數(N) 是不是 質數 :

利用試除法(Trial Division)，找出2到N之間的質數，來一個一個測試N是否能夠被這個範圍的質數整除。

最大公因數

8 的 因數 有 1 、2、 4、 8
4 的 因數 有 1 、 2 、 4
最大公因數 是 4

要怎麼找到 最大公因數 是 4 ?

8 的 質因數 有 2
4 的 質因數 有 2
所以2*2 = 4

這種方法叫短除法，不知道，跳過

來看Euclidean algorithm:

輾轉相除法又稱歐幾里得演算法(Euclidean algorithm)

The Euclidean Algorithm

輾轉相除法 跟 商沒有關係 。
輾轉相除法是不斷的取除數和餘數 。直到餘數是0 ，答案取除數。

現在 要 找 888 和 54 的 最大公因數

888 除以 54 = 16 餘 24
也就是 888 = 54 *16 + 24

之後把 54 和 24 繼續除:
54 = 24 *2 +6

之後把24 和 6 繼續除
24 = 6 *4 + 0

現在餘數 變成0 了 。所以取6 ，答案就是6，最大公因數 就是 6。

來看167,076 和 1,928,737 的最大公因數 :

1,928,737 除以 167,076 = 11 餘 90901

167,076 除以 90901 = 1 餘76175

90901除以 76175 = 1 餘14726

76175除以 14726 = 5 餘2545

14726除以 2545 = 5 餘2001

2545除以 2001 = 1 餘544

2001除以 544 = 3 餘369

544 除以 369 = 1 餘 175

369 除以 175 = 2餘 19

175 除以 9 = 19餘 4

19除以 4 = 4餘 3

4除以 3= 1餘 1

3除以 1 = 3 餘0

所以兩個數 是互質 ，最大公因數是１
程式參考文章中大大寫的部分。

a   =  1928737  
b   =  167076
m   =  1928737  除以167076的餘數

if  (m 不等於 0){
	a   =  b   (原本的除數 變成 被除數)
	b   =  m  (原本的餘數 變成 除數)
    m  =  a % b
}
最後的結果是b (除數)

int m = a % b;   //餘數
while (m != 0) {
    a = b; // 除數
    b = m; //餘數
    m = a % b;  // 除數 和  餘數  相除  ，取餘數
    System.out.print(a +"/"+b+"\n");
}

找最小公倍數

兩數相乘 / 最大公因數

時間複雜度是

不會，先記著。